package com.erbao.datastructurearithmetic.tyro;

import java.util.*;

/**
 * @author CaoBaoYin
 * @since 21/7/29 13:54
 */
public class Class4 {

    public static void main(String[] args) {
        // 验证单链表
        /*int maxLen = 20;
        int maxValue = 100;
        int testTimes = 10000000;
        for (int i = 0; i < testTimes; i++) {
            Node head = generateNodeList(maxLen, maxValue);
            List<Integer> originNodeList = getOriginNodeList(head);
            Node reverseHead = reverseNodeListVzuo(head);

            if (!checkReverseNodeList(reverseHead, originNodeList)) {
                System.out.println("出错了");
                break;
            }
        }
        System.out.println("nice");*/

        // 验证双向链表
        /*int maxLen = 20;
        int maxValue = 100;
        int testTimes = 10000000;
        DoubleNode head = generateDoubleLinkNode(maxLen, maxValue);
        show(head);
        DoubleNode reverseDoubleNodeHead = reverseDoubleNodeList(head);
        show(reverseDoubleNodeHead);*/

        // 验证栈和队列
        /*int maxValue = 100;
        int testTimes = 10000000;
        DoubleQueue<Integer> doubleQueue = new DoubleQueue<>();
        LinkedList<Integer> list = new LinkedList<>();
        Integer res = null;
        Integer resJdk = null;
        for (int i = 0; i < testTimes; i++) {
            double op = Math.random();
            int value = (int) (Math.random() * maxValue) + 1;
            if (op < 0.16) {
                res = resJdk = value;
                doubleQueue.pollHead(value);
                list.add(0, value);
            } else if (op < 0.32) {
                res = resJdk = value;
                doubleQueue.pollTail(value);
                list.add(value);
            } else if (op < 0.48) {
                res = doubleQueue.offerHead();
                resJdk = list.isEmpty() ? null : list.remove(0);
            } else if (op < 0.64) {
                res = doubleQueue.offerTail();
                resJdk = list.isEmpty() ? null : list.remove(list.size()-1);
            } else if (op < 0.8) {
                res = doubleQueue.peekHead();
                resJdk = list.isEmpty() ? null : list.getFirst();
            } else {
                res = doubleQueue.peekTail();
                resJdk = list.isEmpty() ? null : list.getLast();
            }

            if (res == null && resJdk == null) {
                continue;
            }

            if (doubleQueue.size != list.size()) {
                System.out.println("大小不一致");
            }

            if (doubleQueue.isEmpty() != list.isEmpty() ) {
                System.out.println("判空不對");
            }

            if (!res.equals(resJdk)) {
                System.out.println("出錯了！"+op + "res: "+ res + "resJdk: " + resJdk);
                list.toString();
                break;
            }
        }
        System.out.println("nice");*/

        System.out.println(17 / 10);

    }


    private static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }

        ListNode cur1 = l1.val < l2.val ? l1 : l2;//主链表
        ListNode cur2 = cur1 == l1 ? l2 : l1;

        ListNode head = cur1;

        ListNode pre = cur1;
        cur1 = cur1.next;
        while (cur1 != null && cur2 != null) {
            if (cur1.val > cur2.val) {
                pre.next = cur2;
                cur2 = cur2.next;
                pre = pre.next;
                pre.next = cur1;
            } else {
                pre = cur1;
                cur1 = cur1.next;
            }
        }

        if (cur1 == null) {
            pre.next = cur2;
        }

        return head;
    }

    private static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 = lengthListNode(l1);
        int len2 = lengthListNode(l2);
        if (len1 == 0 || len2 == 0) {
            return len1==0 ? l2 : l1;
        }

        ListNode l = len1 > len2 ? l1 : l2;
        ListNode s = l == l1 ? l2 : l1;

        int carry = 0;

        ListNode head = l;
        ListNode tail = null;
        /*while (l != null) {
            tail = l;// 用于最后一位需要新建节点时

            int resultValue;
            if (s != null) {
                resultValue = l.val + s.val + carry;
                s = s.next;
            } else {
                resultValue = l.val + carry;
            }
            carry = resultValue / 10;
            l.val = resultValue % 10;
            l = l.next;
        }*/
        while (s != null) {
            tail = l;// 用于最后一位需要新建节点时
            int resultValue = l.val + s.val + carry;
            carry = resultValue / 10;
            l.val = resultValue % 10;
            l = l.next;
            s = s.next;
        }
        while (l != null) {
            tail = l;// 用于最后一位需要新建节点时
            int resultValue = l.val + carry;
            carry = resultValue / 10;
            l.val = resultValue % 10;
            l = l.next;
        }

        if (carry > 0) {
            tail.next = new ListNode(carry);
        }

        return head;
    }

    private static int lengthListNode(ListNode head) {
        int size = 0;
        while(head != null){
            head = head.next;
            size++;
        }
        return size;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;

        List<ListNode> list = groupK(head, k);
        if (list.size() == 1) return head;

        for (int i = 0; i < list.size(); i++) {
            ListNode headK = list.get(i);
            if (i == 0) {
                ListNode reverseHeadK = reverseNodeList(headK);
                headK.next = list.get(i+1);
                head = reverseHeadK;
            } else if (i!=list.size()-1) {
                ListNode reverseHeadK = reverseNodeList(headK);
                headK.next = list.get(i+1);
                list.get(i-1).next = reverseHeadK;
            } else {
                ListNode tempCursor = headK;
                int tempK = 0;
                while (tempCursor != null) {
                    tempK++;
                    tempCursor = tempCursor.next;
                }
                // 判断最后一组是否需要反转。刚好够K个就需要
                if (tempK == k) {
                    list.get(i-1).next = reverseNodeList(headK);
                }
            }
        }

        return head;
    }

    private static List<ListNode> groupK (ListNode head, int k) {
        if (head == null) return null;

        ArrayList<ListNode> list = new ArrayList<>();

        int size = 0;
        ListNode cursor = head;
        list.add(head);
        while (head != null) {
            cursor = cursor.next;
            size++;
            if (size % k == 0) {
                head.next = null;
                list.add(cursor);
            }
            head = cursor;
        }

        return list;
    }

    private static class DoubleQueue<V> {
        private DoubleLinkNode<V> head;
        private DoubleLinkNode<V> tail;
        private int size;

        public int size () {
            return size;
        }

        public boolean isEmpty () {
            return size == 0;
        }

        public V offerHead() {
            if (head == null) return null;

            V res = head.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.last=null;
            }

            size--;
            return res;
        }

        public V offerTail () {
            if (tail == null) return null;

            V res = tail.value;
            if (head == tail) {
                head = null;
                tail = null;
            } else {
                tail = tail.last;
                tail.next=null;
            }
            size--;
            return res;
        }

        public V pollHead (V value) {
            DoubleLinkNode<V> doubleLinkNode = new DoubleLinkNode<>(value);
            if (head == null) {
                tail = doubleLinkNode;
            } else {
                doubleLinkNode.next = head;
                head.last = doubleLinkNode;
            }
            head = doubleLinkNode;
            size++;
            return head.value;
        }

        public V pollTail (V value) {
            DoubleLinkNode<V> doubleLinkNode = new DoubleLinkNode<>(value);
            if (tail == null) {
                head = doubleLinkNode;
            } else {
                tail.next = doubleLinkNode;
                doubleLinkNode.last = tail;
            }
            tail = doubleLinkNode;
            size++;
            return tail.value;
        }

        public V peekHead () {
            return head==null? null : head.value;
        }

        public V peekTail () {
            return tail == null ? null : tail.value;
        }
    }

    private static class DoubleLinkNode<V> {
        private V value;
        private DoubleLinkNode<V> last;
        private DoubleLinkNode<V> next;

        public DoubleLinkNode(V value) {
            this.value = value;
        }
    }

    /**
     * 单链表实现队列，要从尾进从头出。
     * 减少需要对上一节点操作
     * @param <V>
     */
    private static class Queue<V> {
        private LinkNode<V> head;
        private LinkNode<V> tail;
        private int size;

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        public V peek() {
            return head == null ? null : head.value;
        }

        public V offer() {
            if (head == null) return null;

            LinkNode<V> res = head;

            head = head.next;

            if (head == null) {
                tail = null;
            }

            size--;
            return res.value;
        }

        public V poll(V value) {
            LinkNode<V> linkNode = new LinkNode<>(value);
            if (head == null) {
                head = linkNode;
                tail = linkNode;
            } else {
                tail.next = linkNode;
                tail = tail.next;
            }
            size++;

            return head.value;
        }

        public void show() {
            if (head == null) {
                System.out.println("空链表");
                return;
            }


            do {
                System.out.print(head.value + "  ");
                head = head.next;
            } while (head != null);

            System.out.println();
        }
    }

    private static class Stack<V> {
        private LinkNode<V> head;
        private int size;

        public boolean isEmpty() {
            return size == 0;
        }

        public int size() {
            return size;
        }

        public V peek() {
            return head == null ? null : head.value;
        }

        public V pop() {
            if (head == null) return null;

            LinkNode<V> res = head;

            head = head.next;

            size--;
            return res.value;
        }

        public V push(V value) {
            LinkNode<V> linkNode = new LinkNode<>(value);
            linkNode.next = head;
            head = linkNode;

            size++;

            return head.value;
        }

        public void show() {
            if (head == null) {
                System.out.println("空链表");
                return;
            }


            do {
                System.out.print(head.value + "  ");
                head = head.next;
            } while (head != null);

            System.out.println();
        }
    }

    private static class LinkNode<V> {
        private V value;
        private LinkNode<V> next;

        public LinkNode(V value) {
            this.value = value;
        }

    }

    /**
     * 反转双向链表
     */
    private static DoubleNode reverseDoubleNodeList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 反转单链表
     *
     * @param head 链表头结点
     * @return 反转后的单链表头结点
     */
    private static ListNode reverseNodeList(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;

        // 三个变量位置顺序：pre → head → next
        ListNode pre = null;
        ListNode next = head.next;
        // next == null 表明 head指向了尾结点，反转结束
        while (next != null) {
            head.next = pre;
            pre = head;
            head = next;
            next = next.next;
        }

        head.next = pre;

        return head;
    }

    /**
     * 左老师算法
     */
    private static ListNode reverseNodeListVzuo(ListNode head) {
        ListNode pre = null;
        ListNode next;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 单链表变成list
     *
     * @param head 单链表的头结点
     * @return 单链表顺序list
     */
    private static List<Integer> getOriginNodeList(ListNode head) {
        if (head == null) {
            return null;
        }

        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        return list;
    }

    /**
     * 校验顺序list 和 逆序单链表 是否一致
     *
     * @param head 逆序后的单链表的头结点
     * @param list 单链表的顺序list
     */
    private static boolean checkReverseNodeList(ListNode head, List<Integer> list) {
        if (head == null) return list == null;

        for (int i = list.size() - 1; i >= 0; i--) {
            if (!list.get(i).equals(head.val)) {
                return false;
            }
            head = head.next;
        }

        return true;
    }

    /**
     * 单链表结点
     */
    private static class ListNode {
        private ListNode next;
        private int val;

        public ListNode(int value) {
            this.val = value;
        }

        public ListNode(int[] values) {
            if (values == null) return;

            this.val = values[0];
            ListNode head = this;
            for (int i = 1; i < values.length; i++) {
                head.next = new ListNode(values[i]);
                head = head.next;
            }
        }
    }

    /**
     * 双向链表结点
     */
    private static class DoubleNode {
        private DoubleNode next;
        private int value;
        private DoubleNode last;

        public DoubleNode(int value) {
            this.value = value;
        }
    }

    /**
     * 随机生成一条单链表
     *
     * @param maxLen   链表最大长度
     * @param maxValue 链表最大值
     * @return 头结点
     */
    private static ListNode generateNodeList(int maxLen, int maxValue) {
        int size = (int) (Math.random() * maxLen) + 1;
        if (size == 0) {
            return null;
        }

        size--;
        ListNode head = new ListNode((int) (Math.random() * maxValue) + 1);
        ListNode pre = head;
        while (size > 0) {
            pre.next = new ListNode((int) (Math.random() * maxValue) + 1);
            pre = pre.next;
            size--;
        }
        return head;
    }

    /**
     * 随机产生双向链表
     *
     * @param maxLen   最大长度
     * @param maxValue 最大值
     * @return 双向链表头结点
     */
    private static DoubleNode generateDoubleLinkNode(int maxLen, int maxValue) {
        int size = (int) (Math.random() * maxLen) + 1;
        if (size == 0) {
            return null;
        }

        size--;
        DoubleNode head = new DoubleNode((int) (Math.random() * maxValue) + 1);
        DoubleNode cur = head;
        DoubleNode pre;
        cur.last = null;
        while (size > 0) {
            cur.next = new DoubleNode((int) (Math.random() * maxValue) + 1);
            pre = cur;
            cur = cur.next;
            cur.last = pre;
            size--;
        }
        return head;
    }

    /**
     * 遍历显示单链表
     *
     * @param head 链表头结点
     */
    private static void show(ListNode head) {
        if (head == null) {
            System.out.println("空链表");
            return;
        }


        do {
            System.out.print(head.val + "  ");
            head = head.next;
        } while (head != null);

        System.out.println();

    }

    private static void show(DoubleNode head) {
        if (head == null) {
            System.out.println("空链表！");
            return;
        }

        DoubleNode tail = null;
        while (head != null) {
            System.out.print(head.value + "  ");
            tail = head;
            head = head.next;
        }
        System.out.println();

        while (tail != null) {
            System.out.print(tail.value + "  ");
            tail = tail.last;
        }
        System.out.println();
    }

}
